"""
算法思想：利用堆的特性（大根堆或小根堆）进行排序。首先将数组构建为大根堆，然后反复将堆顶元素（最大元素）与堆尾元素交换，缩小堆的范围并重新调整堆结构，最终得到有序数组。
代码解释：
构建大根堆：从最后一个非叶子节点（索引n//2-1）开始，依次向上调用heap_adjust调整堆结构，使整个数组满足大根堆性质（父节点值大于等于子节点值）。
堆排序主循环：
    每次将堆顶元素（最大元素）与当前堆的最后一个元素交换，将最大元素放到数组末尾。
    堆大小减 1 后，对新的堆顶元素调用heap_adjust，重新维护大根堆性质。
heap_adjust 函数：通过比较父节点与左右孩子节点，将最大元素向上移动，确保子树满足大根堆性质。
时间复杂度：建堆过程为O(n)，排序过程为O(nlogn)，整体时间复杂度为O(nlogn)。
"""


def heap_sort(arr):
    n = len(arr)

    # 构建大根堆（从最后一个非叶子节点开始调整）
    for i in range(n // 2 - 1, -1, -1):
        heap_adjust(arr, i, n)

    # 逐步取出堆顶元素并调整堆
    for i in range(n - 1, 0, -1):
        # 交换堆顶（最大元素）和堆尾元素
        arr[0], arr[i] = arr[i], arr[0]
        # 调整剩余元素为大根堆（堆大小减1）
        heap_adjust(arr, 0, i)

    return arr


def heap_adjust(arr, parent, length):
    """将以parent为根的子树调整为大根堆"""
    # 保存当前父节点的值
    temp = arr[parent]
    # 左孩子节点索引
    child = 2 * parent + 1

    # 遍历子节点
    while child < length:
        # 若右孩子存在且大于左孩子，选择右孩子
        if child + 1 < length and arr[child] < arr[child + 1]:
            child += 1

        # 若父节点大于等于最大孩子，无需调整
        if temp >= arr[child]:
            break

        # 否则将孩子节点的值赋给父节点
        arr[parent] = arr[child]
        # 继续向下调整
        parent = child
        child = 2 * parent + 1

    # 将原父节点的值放到最终位置
    arr[parent] = temp


# 测试
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heap_sort(arr)
print("堆排序结果:", sorted_arr)  # 输出: [5, 6, 7, 11, 12, 13]
